package org.laizili.solution.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <a href="https://leetcode-cn.com/problems/permutations/">46-全排列</a>
 * <p>
 * tags: 递归; 深度优先搜索
 * </p>
 */
public class Problem46 {
    private static class Solution {
        private List<List<Integer>> res = new ArrayList<>();

        public List<List<Integer>> permute(int[] nums) {
            perm(nums, 0, nums.length);
            return res;
        }

        int counter = 0;

        private void perm(int[] num, int left, int right) {
            if (left == right) {
                counter++;
                final ArrayList<Integer> oneRes = Arrays.stream(num).collect(ArrayList::new, List::add, List::addAll);
                res.add(oneRes);
                return;
            }
            for (int i = left; i < right; i++) {
                swap(num, left, i);
                perm(num, left + 1, right);
                swap(num, left, i);
            }
        }

        private static void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}
